//Given an integer array nums and an integer k, return the kth largest element i
//n the array. 
//
// Note that it is the kth largest element in the sorted order, not the kth dist
//inct element. 
//
// 
// Example 1: 
// Input: nums = [3,2,1,5,6,4], k = 2
//Output: 5
// Example 2: 
// Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
//Output: 4
// 
// 
// Constraints: 
//
// 
// 1 <= k <= nums.length <= 104 
// -104 <= nums[i] <= 104 
// 
// Related Topics 堆 分治算法 
// 👍 1064 👎 0


package leetcode.editor.cn;
//Java：Kth Largest Element in an Array
 class P215KthLargestElementInAnArray{
    public static void main(String[] args) {
        Solution solution = new P215KthLargestElementInAnArray().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int findKthLargest(int[] nums, int k) {
        return findKth(nums, 0, nums.length - 1,nums.length- k);
    }
        public  int findKth(int[] a, int start, int end, int k) {
            int pivot = getPivot(a, start, end);
            if (pivot > k) {
                return findKth(a, start, pivot-1, k);
            }
            if (pivot < k) {
                return findKth(a, pivot + 1, end, k);
            } else {
                return a[pivot];
            }
        }
        private  int getPivot(int[] arr, int start, int end) {
            int key = arr[start];
            int low = start;
            int high = end;
            while (low < high) {
                while (low < high && arr[high] >= key) {
                    --high;
                }
                while (low < high && arr[low] <= key) {
                    ++low;
                }
                if (low < high) {
                    swap(arr, low, high);//交换比枢轴小的记录到左端
                }
            }
            swap(arr, start, high);
            return low;
        }
        public  void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
}
//leetcode submit region end(Prohibit modification and deletion)

}